package leetcode.hash;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class UnionFindSet1 {
    public static class Element<V>{
        public V value;

        public Element(V value) {
            this.value = value;
        }
    }
    public static class UnionFindSet<V>{

      public HashMap<V,Element<V>> elementMap;
      public HashMap<Element<V>,Element<V>> fatherMap;
      public HashMap<Element<V>,Integer> rankMap;

      public UnionFindSet(List<V> list){

          elementMap = new HashMap<>();
          fatherMap = new HashMap<>();
          rankMap = new HashMap<>();

          for (V value: list) {
              Element<V> element = new Element<>(value);
              elementMap.put(value,element);
              fatherMap.put(element,element);
              rankMap.put(element,1);
          }

    }
        private Element<V> findHead(Element<V> element){//找头
            Stack<Element<V>> path = new Stack<>();
              while (element!=fatherMap.get(element)){
                  path.push(element);
                  element=fatherMap.get(element);
              }
              while (!path.isEmpty()){
              fatherMap.put(path.pop(),element);
              }
          return element;
        }
        public boolean isSameSet(V a,V b){
            if (elementMap.containsKey(a) && elementMap.containsKey(b)){
                return fatherMap.get(a) == fatherMap.get(b);
            }
            return false;
        }
        public void union(V a,V b){
          if (elementMap.containsKey(a) && elementMap.containsKey(b)){
              Element<V> aF = fatherMap.get(a);
              Element<V> bF = fatherMap.get(b);
              if (aF!=bF){
                  Element<V> big = rankMap.get(aF) >= rankMap.get(bF) ? aF : bF;
                  Element<V> small = big==aF ? bF : aF;
                  fatherMap.put(small,big);
                  rankMap.put(big,rankMap.get(aF)+rankMap.get(bF));
                  rankMap.remove(small);
              }
          }
        }
    }
}
